| |
| description |
20 pages
|
|
We prove that the existential theory of equations with normalized
rational constraints in a fixed graph product of finite monoids,
free monoids, and free groups is PSPACE-complete. Under certain
restrictions this result also holds if the graph product is part of
the input. As the second main result we prove that the positive
theory of equations with recognizable constraints in graph products
of finite and free groups is decidable.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-2001-10/TR-2001-10.ps
|
| contributor |
Theoretische Informatik (IFI)
|
|
| format |
application/postscript
| | 349868 Bytes
| | subject |
Grammars and Other Rewriting Systems (CR F.4.2)
| | Formal Languages (CR F.4.3)
| | relation |
Technical Report No. 2001/10
| |